public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.firstMissingPositive(new int[]{1,2,0}));
        System.out.println(s.firstMissingPositive(new int[]{3,4,-1,1}));
        System.out.println(s.firstMissingPositive(new int[]{7,8,9,11,12}));
    }
}


//官方题解
class Solution {
    public int firstMissingPositive(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            if(nums[i] <= 0){//负数不影响结果，将所有负数变为大于N的正数
                nums[i] = nums.length + 1;
            }
        }

        for(int i = 0; i < nums.length; i++){
            int value = Math.abs(nums[i]);
            if(value <= nums.length){
                nums[value - 1] = -Math.abs(nums[value - 1]);    //用负号做标记，将原数组作为哈希表，表示对应下标的数存在
            }
        }

        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0) {
                return i + 1;
            }
        }
        //N个数正好为1,2,...,N，则答案为N+1
        return nums.length + 1;
    }
}